package com.zlk.algorithm.huawei.leetcode.dp;

import org.junit.Test;

/**
 * @program: algorithm
 * @ClassName Code49_lengthOfLIS
 * @description:
 * 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
 * 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
 * 例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的
 * 子序列
 * 示例 1：
 * 输入：nums = [10,9,2,5,3,7,101,18]
 * 输出：4
 * 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
 * 示例 2：
 *
 * 输入：nums = [0,1,0,3,2,3]
 * 输出：4
 * 示例 3：
 *
 * 输入：nums = [7,7,7,7,7,7,7]
 * 输出：1
 * @author: slfang
 * @create: 2025-01-15 17:19
 * @Version 1.0
 **/
public class Code49_lengthOfLIS {

    @Test
    public void test(){
        int[] arr = new int[]{0,1,0,3,2,3};
        System.out.println(lengthOfLIS(arr));
    }

    //ends数组+二分查找
    // 时间复杂度 n*logN
    //数组  10, 9, 2, 5, 3, 7, 101, 18
    //ends 10
    //dp   1
    //
    //ends 9
    //dp   1   1
    //
    //ends 2
    //dp   1   1  1
    //
    //ends 2   5
    //dp   1   1  1 2
    //
    //ends 2   3
    //dp   1   1  1 2 2
    //
    //ends 2   3  7
    //dp   1   1  1 2 2  3
    //
    //ends 2   3  7 101
    //dp   1   1  1 2 2  3  4
    // final
    //ends 2   3  7 18
    //dp   1   1  1  2  2 3 4 4
    public int lengthOfLIS(int[] arr) {
        int n = arr.length;
        //以i结尾的最长递增子序列长度
        int[] dp = new int[n];
        //长度为 i+1 最nums数
        int r = 0;
        //ends是递增有序的
        int[] ends = new int[n];
        int ans = 1;
        dp[0] = 1;
        ends[0] = arr[0];
        for (int i = 1; i < n; i++) {
            int num = arr[i];
            int left = findLeft(0, r, ends, num);
            if(left>r){
                r++;

            }
            ends[left] = num;
            dp[i] = left+1;
            ans = Math.max(dp[i],ans);
        }
        return ans;
    }

    private int  findLeft(int l, int r, int[] ends, int num) {
        int ans = r+1;
        int m;
        while (l<=r){
            m = l+(r-l)/2;
            if(ends[m]>=num){
                ans = m;
                r = m-1;
            }else{
                l = m+1;
            }
        }
        return ans;
    }


    //最长递增子序列
    // dp[i] 以i结尾最大长递增子序列
    public int lengthOfLIS1(int[] arr) {
        int n = arr.length;
        int[] dp = new int[n];
        dp[0] = 1;
        int ans = 1;
        for (int i = 1; i < n; i++) {
            dp[i]=1;
            for (int j = i-1; j >=0 ; j--) {
                if(arr[i]>arr[j]){
                    dp[i]=Math.max(dp[j]+1,dp[i]);
                }
                ans = Math.max(ans,dp[i]);
            }
        }
        return ans;
    }
}
